/*Copyright (c) Microsoft Open Technologies, Inc.  All rights reserved.
Microsoft Open Technologies would like to thank its contributors, a list
of whom are at https://interview.codeplex.com/team/views.

Licensed under the Apache License, Version 2.0 (the "License"); you
may not use this file except in compliance with the License. You may
obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied. See the License for the specific language governing permissions
and limitations under the License.*/

// Problem:
//     There is a type of singly linked list, data of the node represent an integer between 0 and 9.
//     By this way, a linked list can represent a big integer(maybe more than 20 digits), 
//     the requirement is to plus two linked list by at most twice traverse linked list at worse time
//
// Author: everyday (weijie.he@live.com)
//

#include <iostream>
#include <string>
using namespace std;

struct Node
{
    int data;
    struct Node *next;

    Node(int data, Node *next = nullptr)
        : data(data), next(next)
    {
    }

    Node()
    {
        data = 0;
        next = nullptr;
    }
};

Node *Add(const Node *r1, const Node *r2)
{
    Node *root;
    Node *oldPrevNode = nullptr, *prevNode = nullptr;
    const Node *r1Node = r1, *r2Node = r2;
    bool secondRound = false;

    if (r1Node->data + r2Node->data > 9)
    {
        // Why not create a node with value 1? Because we will deal with it as prevNode in below while loop
        root = new Node();
    }
    else
    {
        root = new Node(r1Node->data + r2Node->data);
        r1Node = r1Node->next;
        r2Node = r2Node->next;
    }
    
    prevNode = root;
    while (r1Node != nullptr)
    {
        Node *currentNode = new Node((r1Node->data + r2Node->data) % 10);

        if (r1Node->data + r2Node->data > 9)
        {
            prevNode->data += (r1Node->data + r2Node->data) / 10;

            if (prevNode->data > 9 &&
                oldPrevNode != nullptr)
            {
                oldPrevNode->data += 1;
                prevNode->data -= 10;

                if (oldPrevNode->data > 9)
                {
                    secondRound = true;
                }
            }
        }

        prevNode->next = currentNode;
        oldPrevNode = prevNode;
        prevNode = currentNode;

        r1Node = r1Node->next;
        r2Node = r2Node->next;
    }

    if (secondRound)
    {
        oldPrevNode = root;
        prevNode = oldPrevNode->next;
        Node *currentNode = prevNode->next;

        do
        {
            if (currentNode->data > 9)
            {
                currentNode->data -= 10;
                prevNode->data += 1;

                if (prevNode->data > 9)
                {
                    oldPrevNode->data += 1;
                    prevNode->data -= 10;
                }
            }

            oldPrevNode = prevNode;
            prevNode = currentNode;
            currentNode = currentNode->next;
        } while (currentNode != nullptr);
    }

    return root;
}

Node *buildNode(string input)
{
    Node *result = new Node;
    Node *temp = result, *prev = result;

    for (size_t i=0; i<input.length(); i++)
    {
        temp->data = input[i] - '0';
        temp->next = new Node;
        prev = temp;
        temp = temp->next;
    }

    prev->next = nullptr;
    delete temp;

    return result;
}

int main(int argc, char* argv[])
{
    Node *r1 = buildNode("1000001");
    Node *r2 = buildNode("9999999");
    Node *root = Add(r1, r2);

    Node *temp = r1;
    while (temp != nullptr)
    {
        cout << temp->data;
        temp = temp->next;
    }

    cout << endl << " + " << endl;

    temp = r2;
    while (temp != nullptr)
    {
        cout << temp->data;
        temp = temp->next;
    }

    cout << endl << " = " << endl;

    temp = root;
    while (temp != nullptr)
    {
        cout << temp->data;
        temp = temp->next;
    }
    cout << endl;

    while (r1 != nullptr)
    {
        temp = r1->next;
        delete r1;
        r1 = temp;
    }

    while (r2 != nullptr)
    {
        temp = r2->next;
        delete r2;
        r2 = temp;
    }

    while (root != nullptr)
    {
        temp = root->next;
        delete root;
        root = temp;
    }

    return 0;
}
